package com.shixianchen.review_the_day_before.day1;

/**
 * @author ShiXianChen
 * @version V1.0.0
 * @Description TODO
 * @date 2022/10/30 13:11
 */
public class Code01_Knapsack {

    public static int maxValue1(int[] weight, int[] value, int bagLimit) {
        return process1(weight, value, 0, bagLimit);
    }

    public static int maxValue2(int[] weight, int[] value, int bagLimit) {
        int length = weight.length;
        int[][] dp = new int[length + 1][bagLimit + 1];


        //先给缓存添加,数据
        for (int i = 0; i <= weight.length; i++) {
            for (int j = 0; j <= bagLimit; j++) {
                dp[i][j] = -2;
            }
        }

        return process2(weight, value, 0, bagLimit, dp);
    }


    public static int process2(int[] weight, int[] value, int index, int rest, int[][] dp) {
        if (rest < 0) {
            return -1;
        }

        //判断缓存中是否含有数据
        if (dp[index][rest] != -2) {
            return dp[index][rest];
        }

        int ans = 0;
        if (weight.length == index) {
            ans = 0;
        } else {
            int p1 = process2(weight, value, index + 1, rest, dp);

            int p2 = -1;

            int next = process2(weight, value, index + 1, rest - weight[index], dp);

            if (next != -1) {
                p2 = value[index] + next;
            }

            ans = Math.max(p1, p2);
        }

        dp[index][rest] = ans;

        return ans;
    }

    public static int process1(int[] weight, int[] value, int index, int rest) {

        //当没有剩余重量时
        if (rest < 0) {
            return -1;
        }


        //当选择完毕时
        if (weight.length == index) {
            return 0;
        }

        //当选择没有完毕时
        //没有选择当前位置的重物

        int p1 = process1(weight, value, index + 1, rest);

        //选择当前位置重物
        //查看下一个位置的选择是否有效

        int p2 = -1;

        int next = process1(weight, value, index + 1, rest - weight[index]);

        if (next != -1) {
            p2 = value[index] + next;
        }
        return Math.max(p1, p2);
    }


}
